# 给定一个二叉树，找出其最大深度。
#  二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
#  说明: 叶子节点是指没有子节点的节点。
#
#  示例：
# 给定二叉树 [3,9,20,null,null,15,7]，
#
#     3
#    / \
#   9  20
#     /  \
#    15   7
#
#  返回它的最大深度 3 。
from com.example.tree.tree_node import TreeNode
from typing import Optional


class Solution:
    def maxDepth2(self, root: Optional[TreeNode]) -> int:
        """
        层序遍历(bfs)
        :param root:
        :return:
        """
        if not root:
            return 0
        queue = [root]
        res = 0
        while queue:
            n = len(queue)  # 记录本层有多少个元素(标识作用，目的是不会出现将下一层的元素在本层遍历时出队)
            while n > 0:  # 依次将本层的元素出队
                if queue[0].left:  # 每个元素出队之前如果它的左右子树不为空则将该元素的左右子树入队(下一层)
                    queue.append(queue[0].left)
                if queue[0].right:
                    queue.append(queue[0].right)
                del queue[0]
                n -= 1
            res += 1  # 一层遍历结束后层数就+1
        return res

    def maxDepth1(self, root: Optional[TreeNode]) -> int:
        """
        dfs(后序遍历)
        :param root:
        :return:
        """
        if not root:  # 递归基：空树的深度为0
            return 0
        leftMaxDepth = self.maxDepth1(root.left)  # 求出左子树的最大深度
        rightMaxDepth = self.maxDepth1(root.right)  # 求出右子树的最大深度
        return max(leftMaxDepth, rightMaxDepth) + 1
        pass

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.maxDepth2(root)


if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(3), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(Solution().maxDepth(root))
